package main

import "fmt"

func mergeSort(arr []int) []int{
	m := len(arr)
	if m < 2 {
		return arr
	}
	mid := m  >> 1
	return merge(mergeSort(arr[:mid]), mergeSort(arr[mid:]))
}

func merge(arr0 []int, arr1 []int) []int{
	i0, i1 := 0, 0
	res := []int{}
	nLen0, nLen1 := len(arr0), len(arr1)
	for i0 < nLen0 || i1 < nLen1{
		if i0 == nLen0{
			res = append(res, arr1[i1])
			i1++
		}else if i1 == nLen1{
			res = append(res, arr0[i0])
			i0++
		}else if arr0[i0] < arr1[i1]{
			res = append(res, arr0[i0])
			i0++
		}else{
			res = append(res, arr1[i1])
			i1++
		}
	}
	fmt.Println(res)
	return  res
}

func main(){
	fmt.Println(mergeSort([]int{1, 3, 2, 3, 6, 7, 5, 10, 11}))

}